package q2155_maxScoreIndices;

import java.util.ArrayList;
import java.util.List;

public class Solution_1 {
    /*
    遍历两次的做法
    先遍历一次即可得到整个数组中一共有多少0和1
    然后再遍历一次 维护两个变量l和r 遇到0 ++l 遇到1 --r 根据l + r更新答案即可
     */
    public List<Integer> maxScoreIndices(int[] nums) {
        int len = nums.length, count_1 = 0, count_0;

        for (int num : nums) count_1 += num;
        count_0 = len - count_1;
        int score = Math.max(count_0, count_1);
        List<Integer> res = new ArrayList<>();

        if (count_0 > count_1) {
            res.add(len);
        } else if (count_0 < count_1) {
            res.add(0);
        } else {
            res.add(0);
            res.add(len);
        }
        int left = 0, right = count_1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == 0) {
                left++;
            } else {
                right--;
            }
            if (left + right > score) {
                res.clear();
                res.add(i + 1);
                score = left + right;
            } else if (left + right == score) {
                res.add(i + 1);
            }
        }
        return res;
    }
}
